package src.BlueBridge.DeepRecursion;

/**
 * 假设我们有8种不同面值的硬币{1, 2, 5, 10, 20, 50, 100, 200}
 * 用这些硬币组合构成一个给定的数值n
 * 例如n=200，那么一种可能的组合方式为200 = 3*1 + 1*2 + 1*5 + 2*20 + 1*50 + 1*100
 * 问总共有多少种可能的组合方式
 */

public class _3硬币表示 {
    public static void main(String[] args) {
//        for (int i = 1 ; i < 101 ; i++) {
//            int ways = countWays(i);
//            System.out.println(i + " --> " + ways);
//        }
        System.out.println(countWaysCore(200, new int[]{1, 5, 10, 25}, 3));
    }

    // 递归形式
    public static int countWays(int n) {
        if (n <= 0)
            return 0;
        return countWaysCore(n, new int[]{1, 5, 10, 25}, 3);
    }
    /**
     *
     * @param n 给定的数值n
     * @param coins 硬币面值
     * @param cur cur是代表剩下有几种面值可以选，从后往前取，也可以理解为对应当前硬币的索引
     * @return
     */
    public static int countWaysCore(int n, int[] coins, int cur) {
        // 考虑出口
        if (cur == 0) {
            return 1;
        }
        // 当前可以选的硬币面值
        // 不选coins[cur]
        // 要一个
        // 要两个...
        int res = 0;
        for (int i = 0 ; i * coins[cur] <= n ; i++) {
            // 剩余的钱数
            int rest = n - i * coins[cur];
            res += countWaysCore(rest, coins, cur - 1);
        }
        return res;
    }

    // 迭代DP
    public static int dp(int n) {
        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[4][n + 1];
        for (int i = 0 ; i < 4 ; i++) {
            dp[i][0]  = 1;
        }
        for (int j = 0 ; j < n + 1 ; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1 ; i < 4 ; i++) {
            for (int j = 1 ; j < n + 1 ; j++) {
                for (int k = 0 ; k <= j / coins[i] ; k++) {
                    dp[i][j] = dp[i - 1][j - k * coins[i]];
                }
            }
        }
        return dp[3][n];
    }
}
